It has become widely accepted to conduct transactions such that as financial transactions or exchange of documents electronically. In order to verify the transaction, it is also well-known to “sign” the transaction digitally so that the authenticity of the transaction can be verified. The signature is performed according to a protocol that utilizes the message, i.e., the transaction, and a secret key associated with the party. Any attempt to tamper with the message or to use a key other than that of the signing party will result in an incompatibility between the message and the signature or will fail to identify the party correctly and thereby lead to rejection of the transaction.
The signature must be performed such that the parties' secret key cannot be determined. To avoid the complexity of distributing secret keys, it is convenient to utilize a public key encryption scheme in the generation of the signature. Such capabilities are available where the transaction is conducted between parties having access to relatively large computing resources but it is equally important to facilitate such transactions at an individual level where more limited computing resources are available.
Automated teller machines (ATMs) and credit cards are widely used for personal transactions and as their use expands, so the need to verify such transactions increases. Transaction cards are now available with limited computing capacity, so-called “Smart Cards,” but these are not sufficient to implement existing digital signature protocols in a commercially viable manner. As noted above, in order to generate a digital signature, it is necessary to utilize a public key encryption scheme. Most public key schemes are based on the Diffie Helman Public key protocol and a particularly popular implementation is that known as DSS. The DSS scheme utilizes the set of integers Zp where p is a large prime. For adequate security, p must be in the order of 512 bits although the resultant signature may be reduced mod q, where q divides p−1, and may be in the order of 160 bits.
The DSS protocol provides a signature composed of two components r, s. The protocol requires the selection of a secret random integer k from the set of integers (0, 1, 2, . . . q−1), i.e.kε{0, 1, 2, . . . q−1).The component r is then computed such thatr={βkmod p}mod q
where β is a generator of q.
The component s is computed ass=[k−1(h(m))+ar]mod q 
where m is the message to be transmitted,                h(m) is a hash of the message, and        a is the private key of the user.        
The signature associated with the message is then sr which may be used to verify the origin of the message from the public key of the user.
The value of βk is computationally difficult for the DSS implementation as the exponentiation requires multiple multiplications mod p. This is beyond the capabilities of a “Smart Card” in a commercially acceptable time. Although the computation could be completed on the associated ATM, this would require the disclosure of the session key k and therefore render the private key, a, vulnerable.
An alternative encryption scheme that provides enhanced security at relatively small modulus is that utilizing elliptic curves in the finite field 2m. A value of m in the order of 155 provides security comparable to a 512 bit modulus for RSA and therefore offers significant benefits in implementation. Diffie Hellman Public Key encryption utilizes the properties of discrete logs so that even if a generator β and the exponentiation βk are known, the value of k cannot be determined.
A similar property exists with elliptic curves where the addition of two points on a curve produces a third point on the curve. Similarly, multiplying a point by an integer k produces a point on the curve.
However, knowing the point and the origin does not reveal the value of the integer ‘n’ which may then be used as a session key for encryption. The value kP, where P is an initial known point, is therefore equivalent to the exponentiation βk.
Elliptic Curve Cryptosystems (ECC) offer advantages over other public key cryptosystems when bandwidth efficiency, reduced computation, and minimized code space are application goals.